Publication Details
Demian Nave and Nikos Chrisochoides.
Published in 17th Canadian Conference on Computational Geometry, pages 282 -- 285, 2005
Abstract
In general, guaranteed-quality Delaunay meshing algorithms are difficult to parallelize because they require strictly ordered updates to the mesh boundary. We show that, by replacing the Delaunay cavity in the Bowyer-Watson algorithm with what we call the circumball intersection set, updates to the mesh can occur in any order, especially at the mesh boundary. To demonstrate this new idea, we describe a 2D constrained Delaunay meshing algorithm that does not enforce strict ordering of vertex insertions near the mesh boundary. We prove that the sequential version of this algorithm generates a mesh in which the circumradius to shortest edge ratio of every triangle is p2 or greater, as long as every angle interior to the polygonal input domain is at least 90o. We briefly touch upon the parallel version of this algorithm, but we relegate a more complete discussion (with extension to 3D) to a forthcoming paper.
